package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/find-duplicate-subtrees/description
 *
 * ```
 * 652. 寻找重复的子树
 * 给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
 * 对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
 * 如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
 *
 * 示例 1：
 * 输入：root = [1,2,3,4,null,2,4,null,null,4]
 * 输出：[[2,4],[4]]
 *
 * 示例 2：
 * 输入：root = [2,1,1]
 * 输出：[[1]]
 *
 * 示例 3：
 * 输入：root = [2,2,2,3,null,3,null]
 * 输出：[[2,3],[3]]
 *
 * 提示：
 * 树中的结点数在 [1, 5000] 范围内。
 * -200 <= Node.val <= 200
 * ```
 */
class leetcode_652 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n2_2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n4_2 = TreeNode(4)
        val n4_3 = TreeNode(4)

        val root = n1
        n1.left = n2
        n1.right = n3
        n2.left = n4
        n3.left = n2_2
        n3.right = n4_2
        n2_2.left = n4_3
        val actual = findDuplicateSubtrees(root)
        val expected = arrayListOf(n4_3, n2_2)
        Assert.assertEquals(expected.size, actual.size)
        for (i in 0 until actual.size) {
            Assert.assertEquals(actual[i], expected[i])
        }
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n1_2 = TreeNode(1)
        val n2 = TreeNode(2)

        val root = n2
        n2.left = n1
        n2.right = n1_2
        val actual = findDuplicateSubtrees(root)
        val expected = arrayListOf(n1_2)
        Assert.assertEquals(expected.size, actual.size)
        for (i in 0 until actual.size) {
            Assert.assertEquals(actual[i], expected[i])
        }
    }

    @Test
    fun test_3() {
        val n2 = TreeNode(2)
        val n2_2 = TreeNode(2)
        val n2_3 = TreeNode(2)

        val n3 = TreeNode(3)
        val n3_2 = TreeNode(3)

        val root = n2
        n2.left = n2_2
        n2.right = n2_3
        n2_2.left = n3
        n2_3.left = n3_2

        val actual = findDuplicateSubtrees(root)
        val expected = arrayListOf(n3_2, n2_3)
        Assert.assertEquals(expected.size, actual.size)
        for (i in 0 until actual.size) {
            Assert.assertEquals(actual[i], expected[i])
        }
    }


    private fun findDuplicateSubtrees(root: TreeNode?): List<TreeNode?> {
        /**
        题型：二叉树的后序遍历 + 哈希法
        思路：
        把当前节点和左右子树的组装string 存放在map中，若这个组装string第2个出现，说明重复子树第1次出现，则收集起来。
        https://leetcode.cn/problems/find-duplicate-subtrees/solutions/1801809/by-ac_oier-ly58
         */
        f(root)
        return result
    }


    // key = 当前节点和左右子树的组装string
    // value，key 出现的次数
    private val map: HashMap<String, Int> = HashMap()
    private val result: ArrayList<TreeNode?> = ArrayList()
    private fun f(root: TreeNode?): String {
        // 1 确认函数参数以及返回值
        // 2 确认终止条件
        if (null == root) {
            return ""
        }

        // 3 确认单层递归的处理逻辑：左右中
        // 左
        val left = f(root.left)

        // 右
        val right = f(root.right)

        // 中
        // 把当前节点和左右子树的组装string，若判断count == 2，说明重复子树第1次出现了，要收集起来
        val str: String = "#" + root.`val` + "|" + left + "|" + right
        map.put(str, (map[str] ?: 0) + 1)
        if (map[str] == 2) { // 重复子树第1次出现，要收集起来
            result.add(root)
        }
        return str
    }
}